/*
Date:20210416 12:52pm
key:从右往左，第一个下降处，保留下降者坐标。从右往左，第一个大于下降者处，交换二者，并从下降者处开始对后面sort，因为后面要升序排列才是最小的。
*/

class Solution {
public:
    void swap(int&a,int&b)
    {
        int k=a;
        a=b;
        b=k;
    }
    void res(vector<int>& nums,int i,int j)
    {

        while(i<j)
        {
            swap(nums[i],nums[j]);
            i++;
            j--;
        }
    }
    void nextPermutation(vector<int>& nums) {
        
        bool flag=1;
        int k;
        //从右往左找第一个下降的
        for(int i=nums.size()-1;i>0;i--)
        {
            if(nums[i]>nums[i-1])
            {
                k=i-1;
                flag=0;
                //swap(nums[i],nums[i-1]);
                break;
            }
        }
        //一个都找不到证明是升序
        if(flag)
        {
            res(nums,0,nums.size()-1);
            return;
        }


        //从右往左找第一个大于k的
        for(int i=nums.size()-1;i>0;i--)
        {
            if(nums[k]<nums[i])
            {
                
                swap(nums[k],nums[i]);

                sort(nums.begin()+k+1, nums.end());
                break;
            }
        }
    }
};